#ifndef LOCKED_THREAD_SAFE_QUEUE_HPP
# define LOCKED_THREAD_SAFE_QUEUE_HPP

#include <mutex>
#include <memory>
#include <condition_variable>

#ifdef DEBUG
    #include <cstdio>
    #include <iostream>
#endif

/*
    基于锁和链表的线程安全队列，
    提供了4个出队列方法，一个入队列方法
*/

// 因为这个类有一个 std::unique_ptr<?> 类变量
// 因此，不能用 std::shared_ptr<node> 类变量指向这个类的对象



template<typename T>
class thread_safe_queue
{
public:
    struct node
    {
        // 要存储的元素的指针
        std::shared_ptr<T> data;
        std::unique_ptr<node> next;
    };
public:
    // 取出队列中第一个节点，如果队列为空，不等待
    std::shared_ptr<T> try_pop()
    {
        std::unique_ptr<node> old_head = try_pop_head();
        // 注意这里返回的不是 std::unique_ptr<node>，而是 std::shared_ptr<T>
        return old_head ? old_head->data : std::shared_ptr<T>();
    }

    bool try_pop(T& value)
    {
        std::unique_ptr<node> const old_head = try_pop_head(value);
        // 虽然 old_head 的类型为 std::unique_ptr<?>，但可以强制转换为 bool 值
        return bool(old_head);
    }

private:
    // 返回队列头结点的指针
    // 注意，虽然std::unique_ptr<?>是不可复制的，但可以作为函数返回值返回
    std::unique_ptr<node> try_pop_head()
    {
        // 对队列的头节点加锁
        std::lock_guard<std::mutex> head_lock(head_mutex);
        if(head.get() == get_tail())
        {
            return std::unique_ptr<node>();
        }
        return pop();
    }

    // 返回队列头结点的指针，把节点头节点指向的内容移动给value
    std::unique_ptr<node> try_pop_head(T& value)
    {
        // 对队列的头节点加锁
        std::lock_guard<std::mutex> head_lock(head_mutex);
        if(head.get() == get_tail())
        {
            return std::unique_ptr<node>();
        }
        value = std::move( *(head->data) );
        return pop();
    }
    
public:
    // 取出队列中第一个节点，如果队列为空，等待
    std::shared_ptr<T> wait_pop()
    {
        std::unique_ptr<node> const old_head = wait_head();
        return old_head->data;
    }

    bool wait_pop(T& value)
    {
        std::unique_ptr<node> const old_head = wait_head(value);
        return bool(old_head);
    }

private:
    std::unique_ptr<node> wait_head()
    {
        std::unique_lock<std::mutex> head_lock(wait_for_data());
        return pop();
    }

    // 弹出队列的头元素，并把这个元素移动到传入的参数T & value中
    std::unique_ptr<node> wait_head(T& value)
    {
        // 把 wait_for_data() 函数传出来的队列头节点的互斥量的锁对象，
        // 移动给这个队列头节点的互斥量的锁对象。在这个过程中，一直
        // 没有调用这个锁对象的析构函数，因此执行这些代码的线程一直持有互斥量。
        std::unique_lock<std::mutex> head_lock(wait_for_data());
        value = std::move(*head->data);
        return pop();
    }

    std::unique_lock<std::mutex> wait_for_data()
    {
        // 给队列头节点的互斥量加锁
        std::unique_lock<std::mutex> head_lock(head_mutex);
        // 使用Lambda函数对条件变量进行等待，而不使用 notify
        data_cond.wait(head_lock, [&]{
                return head.get() != get_tail();
            });
        // 将锁的实例返回给调用者
        return std::move(head_lock);
    }

private:
    // 弹出头结点, 返回头节点的指针。
    // 注意，虽然std::unique_ptr<?>是不可复制的，但可以作为函数返回值返回
    std::unique_ptr<node> pop()
    {
        // 得到队列头节点的指针，最后把这个指针返回
        std::unique_ptr<node> old_head = std::move(head);
        // 把队列头结点设为当前头节点的next节点
        head = std::move(old_head->next);
        return old_head;
    }

public:
    // 向队列加入新的节点，节点存储的是传入的值。
    // 传入的值是一个T类型的对象，而不是一个引用。
    void push(T new_value)
    {
        std::shared_ptr<T> new_data(std::make_shared<T>(std::move(new_value)));
        // 因为本来的队列尾虚拟node要指向一个数据项了，因此这里新建一个队列尾虚拟node
        // 新建一个节点，并且加入队列尾部。
        std::unique_ptr<node> p(new node);
        {
            // 对队列尾的互斥量加锁
            std::lock_guard<std::mutex> tail_lock(tail_mutex);
            // 在原来的尾节点中存储传入的值
            tail->data = new_data;
            node * const new_tail = p.get();
            // 使原来的尾节点的next指针指向新创建的节点
            tail->next = std::move(p);
            // 新创建的节点变为新的尾节点
            tail = new_tail;
        }
        data_cond.notify_one();
    }

// 数据域
private:
    // 访问队列头结点的互斥量
    std::mutex head_mutex;
    // 
    std::unique_ptr<node> head;
    // 访问队列尾节点的互斥量
    std::mutex tail_mutex;
    // 这个指针指向队列的尾节点
    // 队列中的尾节点不存储元素，也就是 tail->data == null，作为标志节点。
    node * tail;
    std::condition_variable data_cond;

public:
    // 唯一的可用的构造函数
    thread_safe_queue(): head(new node), tail(head.get()) {}
    
    // 线程安全的检测队列是否为空，它对队列的头节点互斥量、尾节点互斥量都加锁
    bool empty()
    {
        std::lock_guard<std::mutex> head_lock(head_mutex);
        return (head.get() == get_tail());
    }

    // 线程安全的获得队列的尾部节点
    node * get_tail()
    {
        // 获得 队列尾虚拟node的指针，需要对 队列尾的mutex 加锁
        std::lock_guard<std::mutex> tail_lock(tail_mutex);
        return tail;
    }

    // 不允许 拷贝构造
    thread_safe_queue(const thread_safe_queue& other) = delete;
    // 不允许 赋值操作
    thread_safe_queue& operator = (const thread_safe_queue& other) = delete;
};

#endif
